#include <iostream>
#include "../head/TreeNode.h"

using namespace std;


// 257. Binary Tree Paths
// 时间复杂度: O(n), n为树中的节点个数 空间复杂度: O(h), h为树的高度
class Solution {
public:
	vector<string> binaryTreePaths(TreeNode* root) {
		vector<string> res;
		if(root == NULL) return res;

		if(root->left == NULL && root->right == NULL){
			res.push_back(to_string(root->val));
			return res;
		}

		vector<string> leftPaths = binaryTreePaths(root->left);
		for(int i = 0 ; i < leftPaths.size() ; i ++)
            res.push_back(to_string(root->val) + "->" + leftPaths[i]);

        vector<string> rightPaths = binaryTreePaths(root->right);
        for(int i = 0 ; i < rightPaths.size() ; i ++)
            res.push_back(to_string(root->val) + "->" + rightPaths[i]);

        return res;
    }
};
